/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package puzzleevolution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 *
 * @author vorispe1
 */
public class Evolution {


    /**
     * Metoda zamicha poradi id dilku a vytvori nove jedince s takto zamichanymi dilky
     *
     * @param puzzle
     */
    public ArrayList<Chromosome> firstGeneration(PuzzlePiece[][] puzzle){
        ArrayList<Chromosome> prvniPopulace = new ArrayList();

        for (int i=0; i < Config.velikostPopulace; i++){
            Chromosome jedinec = new Chromosome(puzzle);

            jedinec.setPuzzlePossibleSolution(shuffle(jedinec).getPuzzlePossibleSolution());

            jedinec.setId(i);
            jedinec.calculateFitness();
            prvniPopulace.add(jedinec);
        }
        return prvniPopulace;
    }

    /**
     * Misto nasobeni prvky scita
     *
     * @param n
     * @return
     */
    public static long pseudoFactorial( int n )
    {
        if( n <= 1 )
            return 1;
        else
            return n + pseudoFactorial( n - 1 );
    }


    /**
     * Vyber jedincu z populace pomoci rank ruletove metody. plocha na rulete se rovnomerne rozdeli podle poradi jedincu podle fitness. ne primo podle fitness hodnoty.
     * pro pet soutezicich jsou horni hranice intervalu nasledujici
     * 0    0.066
     * 1    0.200
     * 2    0.400
     * 3    0.666
     * 4    1.000
     *
     * Padne-li cislo 0.00001, je vybran prvni soutezici. Kdyz padne 0.758, je vybran posledni soutezici, ktery ma nejlepsi fitness.
     */
    public Chromosome rankRulette(int pocetSoutezicich, ArrayList<Chromosome> populace){
        ArrayList<Chromosome> soutezici = new ArrayList();
        double vyherniHladina = 0;
        double jednotka;
        jednotka = (double) 1 / (double) pseudoFactorial(pocetSoutezicich); // 1 lomeno pseudoFactorial poctu soutezicich

        //nahodny vyber n jedincu z populace
        for (int i=0; i < pocetSoutezicich; i++){
            soutezici.add(populace.get((int) (Math.random() * (Config.velikostPopulace - 1))));
        }

        //serazeni soutezicich od nejhorsiho - s nejvetsi fitness, tedy s nejvice rozdily hran
        Collections.sort(soutezici, new Comparator<Chromosome>() {
        @Override public int compare(Chromosome p1, Chromosome p2) {
            return (int) (p2.getFitness() - p1.getFitness());
        }});

        //roztoceni rulety
        double vyherniCislo = Math.random();

        //urceni vyherce
        for (int i=0; i < pocetSoutezicich; i++){    //scitame fitness souteznich jedincu
            vyherniHladina += jednotka * (i+1);
            if (vyherniCislo < vyherniHladina){
                return soutezici.get(i);    //kdyz suma prekroci vyherni cislo, vratime aktualniho souteziciho
            }
        }

        System.out.println("rankRuleta nic nevybrala. Vratila prvniho souteziciho");
        return soutezici.get(0);  //pri selhani vratime prvniho souteziciho
    }



    /**
     * jednorodicovske metody krizeni jedince
     *
     */
    public Chromosome crossover(Chromosome rodic){
        Chromosome vystupniJedinec = new Chromosome();

        PuzzlePiece[][] rodicovyDilky = new PuzzlePiece[Config.pocetDilkuX][Config.pocetDilkuY];
        PuzzlePiece[][] potomkovyDilky = new PuzzlePiece[Config.pocetDilkuX][Config.pocetDilkuY];

        rodicovyDilky = rodic.getPuzzlePossibleSolution();

        double typKrizeni = 0;
        typKrizeni = Math.random();

        if (typKrizeni < 0.4){
                    //vymena sousednich dilku vedle sebe
                    //mala zmena jedince - pouzivat casto

                    PuzzlePiece temp = new PuzzlePiece();
                    PuzzlePiece temp2 = new PuzzlePiece();

                    int x = (int) (Math.random() * (Config.pocetDilkuX - 1));
                    int y = (int) (Math.random() * (Config.pocetDilkuY));

                    temp = rodicovyDilky[x][y];
                    vystupniJedinec.setPuzzlePossibleSolution(rodicovyDilky);

                    temp2 = rodicovyDilky[x+1][y];
                    vystupniJedinec.getPuzzlePossibleSolution()[x+1][y] = temp;
                    vystupniJedinec.getPuzzlePossibleSolution()[x][y]   = temp2;

                    vystupniJedinec.setId(rodic.getId());
                    return vystupniJedinec;
                }
        else if (typKrizeni < 0.8){
                    //vymena sousednich dilku nad sebou
                    //mala zmena jedince - pouzivat casto

                    PuzzlePiece temp = new PuzzlePiece();
                    PuzzlePiece temp2 = new PuzzlePiece();

                    int x = (int) (Math.random() * (Config.pocetDilkuX));
                    int y = (int) (Math.random() * (Config.pocetDilkuY - 1));

                    temp = rodicovyDilky[x][y];
                    vystupniJedinec.setPuzzlePossibleSolution(rodicovyDilky);

                    temp2 = rodicovyDilky[x][y+1];
                    vystupniJedinec.getPuzzlePossibleSolution()[x][y+1] = temp;
                    vystupniJedinec.getPuzzlePossibleSolution()[x][y]   = temp2;

                    vystupniJedinec.setId(rodic.getId());
                    return vystupniJedinec;
                }                
        else if (typKrizeni < 0.88){
                    //vymena dvou radku
                    //silna operace - pouzivat zridka

                    int radekA = (int) Math.round(Math.random() * (Config.pocetDilkuX - 1));
                    int radekB = (int) Math.round(Math.random() * (Config.pocetDilkuX - 1));

                    //pokud se vygenerovaly shodne body, dojde k uprave
                    if (radekA == radekB) {
                        if (radekA+1 >= Config.pocetDilkuX){radekA--;}
                        else {radekA++;}
                    }

                    //vymena dilku
                    for (int i=0; i < Config.pocetDilkuY; i++){
                        for (int j=0; j < Config.pocetDilkuY; j++){
                            if (j == radekA) {
                                potomkovyDilky[i][j] = rodicovyDilky[i][radekB];}
                            else if(j == radekB) {
                                potomkovyDilky[i][j] = rodicovyDilky[i][radekA];
                            }
                            else {
                                potomkovyDilky[i][j] = rodicovyDilky[i][j];
                            }
                        }
                    }
                    vystupniJedinec.setPuzzlePossibleSolution(potomkovyDilky);
                    vystupniJedinec.setId(rodic.getId());
                    return vystupniJedinec;
                }
        else if (typKrizeni < 0.96){
                    //vymena dvou sloupcu
                    //silna operace - pouzivat zridka

                    int sloupecA = (int) Math.round(Math.random() * (Config.pocetDilkuY - 1));
                    int sloupecB = (int) Math.round(Math.random() * (Config.pocetDilkuY - 1));

                    //pokud se vygenerovaly shodne body, dojde k uprave
                    if (sloupecA == sloupecB) {
                        if (sloupecA+1 >= Config.pocetDilkuX){sloupecA--;}
                        else {sloupecA++;}
                    }

                    //vymena dilku
                    for (int i=0; i < Config.pocetDilkuY; i++){
                        for (int j=0; j < Config.pocetDilkuY; j++){
                            if (i == sloupecA) {potomkovyDilky[i][j] = rodicovyDilky[sloupecB][j];}
                            else
                                if (i == sloupecB) {potomkovyDilky[i][j] = rodicovyDilky[sloupecA][j];}
                            else
                            {
                                potomkovyDilky[i][j] = rodicovyDilky[i][j];
                            }
                        }
                    }
                    vystupniJedinec.setPuzzlePossibleSolution(potomkovyDilky);
                    vystupniJedinec.setId(rodic.getId());
                    return vystupniJedinec;
                }
        else if (typKrizeni < 0.98){
                    //prepsani bloku naruby
                    //  1 2 3      9 8 7
                    //  4 5 6  na  6 5 4
                    //  7 8 9      3 2 1
                    //funguje pro libovolne rozmery bloku
                    //velmi agresivni operace - pouzivat vyjimecne

                    int radekA = (int) Math.round(Math.random() * (Config.pocetDilkuX - 1));
                    int radekB = (int) Math.round(Math.random() * (Config.pocetDilkuX - 1));

                    int sloupecA = (int) Math.round(Math.random() * (Config.pocetDilkuY - 1));
                    int sloupecB = (int) Math.round(Math.random() * (Config.pocetDilkuY - 1));

                    int bodAx, bodAy, bodBx, bodBy;

                    //pripadne prepsani tak aby prvni bod mel nizsi hodnoty nez druhy
                    if (sloupecA > sloupecB) {bodBy = sloupecA; bodAy = sloupecB;}
                    else {bodBy = sloupecB; bodAy = sloupecA;}
                    if (radekA > radekB) {bodBx = radekA; bodAx = radekB;}
                    else {bodBx = radekB; bodAx = radekA;}

                    //pokud se vygenerovaly shodne body, dojde k uprave
                    if (bodAx == bodAy && bodAy== bodBx && bodAy== bodBy){
                        if (bodBy+1 >= Config.pocetDilkuX){bodAy--;}
                            else {bodBy++;}
                    }

                    //vymena dilku
                    for (int i=0; i < Config.pocetDilkuY; i++){
                        for (int j=0; j < Config.pocetDilkuX; j++){
                            if (i >= bodAy && i <= bodBy && j >= bodAx && j <= bodBx) {
                                potomkovyDilky[i][j] = rodicovyDilky[bodAy + bodBy - i][bodAx + bodBx - j];
                            }
                            else {
                                potomkovyDilky[i][j] = rodicovyDilky[i][j];
                            }
                        }
                    }
                    vystupniJedinec.setPuzzlePossibleSolution(potomkovyDilky);
                    vystupniJedinec.setId(rodic.getId());

                    return vystupniJedinec;
                }
                else {
                    //zcela nahodne zamichani celeho reseni
                    //velmi agresivni operace - pouzivat vyjimecne

                    return shuffle(rodic);
                }
   }


    /**
     * Metoda vzajemne prohodi dva nahodne dilky jedince
     *
     * @param jedinec
     * @return
     */
    public PuzzlePiece[][] mutate(Chromosome jedinec){
        PuzzlePiece[][] vystupniJedinec = new PuzzlePiece[Config.pocetDilkuX][Config.pocetDilkuY];

        //nahodny vyber souradnic dvou dilku
        int xA = (int) Math.round(Math.random() * (Config.pocetDilkuX - 1));
        int yA = (int) Math.round(Math.random() * (Config.pocetDilkuY - 1));

        int xB = (int) Math.round(Math.random() * (Config.pocetDilkuX - 1));
        int yB = (int) Math.round(Math.random() * (Config.pocetDilkuY - 1));

        PuzzlePiece[][] vstupniDilky = new PuzzlePiece[Config.pocetDilkuX][Config.pocetDilkuY];

        PuzzlePiece a = new PuzzlePiece();
        PuzzlePiece b = new PuzzlePiece();

        vstupniDilky = jedinec.getPuzzlePossibleSolution();

        a = vstupniDilky[xA][yA];
        b = vstupniDilky[xB][yB];

        //vymena dilku
        vstupniDilky[xA][yA] = b;
        vstupniDilky[xB][yB] = a;

        vystupniJedinec = vstupniDilky;
        return vystupniJedinec;
    }


    /**
     * Metoda vrati nahodne zamichane dilky
     *
     * @param rodicovyDilky
     * @return
     */
    public Chromosome shuffle(Chromosome rodic){
        PuzzlePiece[] temp = new PuzzlePiece[Config.pocetDilkuY * Config.pocetDilkuX];
        Chromosome vystupniJedinec = new Chromosome();

        System.arraycopy(vystupniJedinec.toArray(rodic.getPuzzlePossibleSolution()), 0, temp, 0, temp.length);  //prevedeni na pole
        Collections.shuffle(Arrays.asList(temp));       //zamichani pole
        vystupniJedinec.setPuzzlePossibleSolution(vystupniJedinec.toMatrix(temp));  //prevedeni zpet na matici

        vystupniJedinec.setId(rodic.getId());
        vystupniJedinec.calculateFitness();
        return vystupniJedinec;
    }


    public void showFitnesses(ArrayList<Chromosome> populace){
        for (int i=0; i < populace.size(); i++){
            System.out.print(populace.get(i).getFitness()+", ");
        }
    }


    public double sumOfFitnesses(Chromosome[] populace){
        double suma = 0;

        for (int i=0; i < populace.length; i++){
                suma += populace[i].getFitness();
        }
        return suma;
    }



    /**
     * Metoda vypise statistiku generace a vrati pozici nejlepsiho jedince
     *
     * @param populace
     * @return
     */
    public int showStatistic(ArrayList<Chromosome> populace){
        double min = 999999999;
        double suma = 0;
        int nejlepsi = 0;
        double prumer = 0;

        for (int i=0; i < populace.size(); i++){
                if (populace.get(i).getFitness() < min){ min = populace.get(i).getFitness(); nejlepsi = i;}
                suma += populace.get(i).getFitness();
        }

        prumer = Math.round(suma / (double) Config.velikostPopulace);
        Config.uspesnost = Math.round(((Config.spravnaFitness) / min) * 100); 
        System.out.println("Nejlepsi a prumerna fitness v populaci jsou: "+min+"   "+prumer+"   spravna fitness: "+Config.spravnaFitness+"   "+Config.uspesnost+"% "+Config.pravdepodobnostMutace);

        return nejlepsi;
    }


    /**
     * Metoda vrati nejlepsiho jedince z cele populace
     * @return
     */
    public static Chromosome pickBestChromosome(ArrayList<Chromosome> populace){
        Chromosome nejlepsiJedinec = new Chromosome();
        ArrayList<Chromosome> jedinci = new ArrayList();
        jedinci = populace;

        //serazeni jedincu od nejlepsiho - s nejmensi fitness
        Collections.sort(jedinci, new Comparator<Chromosome>() {
        @Override public int compare(Chromosome p1, Chromosome p2) {
            return (int) (p1.getFitness() - p2.getFitness());
        }});

        nejlepsiJedinec = jedinci.get(0);
        return nejlepsiJedinec;
    }


    /**
     * Metoda vrati pozici nejhorsiho jedince.
     *
     * @param populace
     * @return
     */
    private int nejslabsi(ArrayList<Chromosome> populace){
    float max = -999999999;
    int nejslabsi = 0;
    for (int i = 0; i < populace.size(); i++)
        {
            if(max < populace.get(i).getFitness()) {
                max = populace.get(i).getFitness();
                nejslabsi = i;
            }
        }
    return nejslabsi;
}


    /**
     * Metoda provadejici vlastni evoluci
     * 
     * @param originalPuzzle
     */
    public void Evolution(PuzzlePiece[][] originalPuzzle){
        long startovniCas;

if (Config.typEvoluce == 0){
        Chromosome puvodniObraz = new Chromosome();
        puvodniObraz.setPuzzlePossibleSolution(originalPuzzle);
        Config.puvodniObraz = puvodniObraz;
        puvodniObraz.calculateFitness();
        Config.spravnaFitness = puvodniObraz.getFitness();  //pro potreby nekterych typu pocitani fitness ulozime hledanou hodnotu fitness
        System.out.println("Fitness spravne slozeneho obrazu je: "+puvodniObraz.getFitness());
        //ResultPicture.drawAll(puvodniObraz.getPuzzlePossibleSolution());

/*
        PuzzlePiece.showOnePiece(puvodniObraz.getPuzzlePossibleSolution()[0][0]);
        System.out.println();
        PuzzlePiece.showOnePiece(puvodniObraz.getPuzzlePossibleSolution()[0][1]);
        System.out.println();
        PuzzlePiece.showOnePiece(puvodniObraz.getPuzzlePossibleSolution()[1][0]);
        System.out.println();
        PuzzlePiece.showOnePiece(puvodniObraz.getPuzzlePossibleSolution()[1][1]);
        System.out.println();*/

        Chromosome druhyJedinec = new Chromosome(puvodniObraz);/*
        druhyJedinec.getPuzzlePossibleSolution()[0][0] = originalPuzzle[0][0];
        druhyJedinec.getPuzzlePossibleSolution()[0][1] = originalPuzzle[1][0];
        druhyJedinec.getPuzzlePossibleSolution()[1][0] = originalPuzzle[0][1];
        druhyJedinec.getPuzzlePossibleSolution()[1][1] = originalPuzzle[1][1];*/
        druhyJedinec.setPuzzlePossibleSolution(shuffle(puvodniObraz).getPuzzlePossibleSolution());
        //druhyJedinec = crossover(druhyJedinec);
        druhyJedinec.calculateFitness();
/**=
        for (int i=0; i < Config.delkaDilku; i++){

            for (int j=0; j < Config.delkaDilku; j++){
                System.out.print(puvodniObraz.getPuzzlePossibleSolution()[1][1].getPieceImage()[i][j].getGreen()+" ");
            }System.out.println();
        }*/
  /*      for (int i=0; i < Config.delkaDilku; i++){
            System.out.print(druhyJedinec.getPuzzlePossibleSolution()[1][0].getDown()[i].getRed()+" ");
        }System.out.println();
        for (int i=0; i < Config.delkaDilku; i++){
            System.out.print(druhyJedinec.getPuzzlePossibleSolution()[0][1].getLeft()[i].getBlue()+" ");
        }System.out.println();*/
        
        System.out.println("druhyJedinec.calculateFitness: "+druhyJedinec.getFitness());
        ResultPicture.drawAll(puvodniObraz.getPuzzlePossibleSolution());
        //ResultPicture.drawAll(druhyJedinec.getPuzzlePossibleSolution());
        System.out.println();
        Config.verzeFitness = 0;
        Chromosome qwer = new Chromosome(druhyJedinec);
        qwer.calculateFitness();
        System.out.println("Manhattanska vzdalenost nejlepsiho jedince: "+qwer.getFitness()); //vypsani fitness nejlepsiho pomoci manhattanovskych vzdalenosti
}
else if (Config.typEvoluce == 1){
        Chromosome puvodniObraz = new Chromosome();
        ArrayList<Chromosome> populace;
        int cisloPopulace = 0;

        //nastaveni nulteho jedince, ktery nese spravne reseni
        puvodniObraz.setPuzzlePossibleSolution(originalPuzzle);
        puvodniObraz.calculateFitness();

        System.out.println("Fitness spravne slozeneho obrazu je: "+puvodniObraz.getFitness());
        Config.spravnaFitness = puvodniObraz.getFitness();  //pro potreby nekterych typu pocitani fitness ulozime hledanou hodnotu fitness
        //Config.puvodniObraz = puvodniObraz;
        System.out.println();

        startovniCas = System.currentTimeMillis();

        //vytvoreni prvni generace zamichanim puvodniho obrazu
        populace = (firstGeneration(originalPuzzle));

        showStatistic(populace);

        while( pickBestChromosome(populace).getFitness() > Config.spravnaFitness ){    //(cisloPopulace + 1) < Config.pocetPopulaci
            System.out.print((cisloPopulace+1)+".generace. ");
            double osudJedince = 0;

            //prochazime celou populaci a kazdeho jedince bud zmutujeme nebo zkrizime nebo zachovame
            for (int i=0; i < Config.velikostPopulace; i++){

                //rozhodne, zda se bude jedinec mutovat nebo krizit
                osudJedince = Math.random();
                //vytvorim novy Chromosome do ktereho zkopiruji aktualni Chromosome z populace, provedu na nem operace a pokud ho to zlepsi vymenim ho za toho v populaci
                Chromosome kandidat = new Chromosome(populace.get(i));

                if (osudJedince < Config.pravdepodobnostMutace){
                    //mutace
                    mutate(kandidat);
                    kandidat.calculateFitness();
                }
                else if (osudJedince < 1){
                    //krizeni
                    crossover(kandidat);
                    kandidat.calculateFitness();
                }

                //pokud je kandidat lepsi nez puvodni jedinec, vymeni se
                if (kandidat.getFitness() < populace.get(i).getFitness()){
                    populace.set(i, kandidat);
                }
            }

            showStatistic(populace);
            cisloPopulace++;
        }
        //Vypsani doby behu programu
        long konecnyCas = System.currentTimeMillis();
        long dobaBehuProgramu = (konecnyCas- startovniCas);
        System.out.println("Doba behu programu: "+ dobaBehuProgramu+" milisekund.");

        //vykresleni nalezeneho nejlepsiho reseni
        ResultPicture.drawAll(pickBestChromosome(populace).getPuzzlePossibleSolution());

        //spocitani manhattanske vzdalenosti nejlepsiho reseni
        System.out.println();
        Config.verzeFitness = 0;
        Chromosome qwer = new Chromosome(pickBestChromosome(populace));
        qwer.calculateFitness();
        System.out.println("Manhattanska vzdalenost nejlepsiho jedince: "+qwer.getFitness()); //vypsani fitness nejlepsiho pomoci manhattanovskych vzdalenosti
    }
else if (Config.typEvoluce == 2){
        Chromosome puvodniObraz = new Chromosome();
        ArrayList<Chromosome> populace;
        int cisloPopulace = 0;

        //nastaveni nulteho jedince, ktery nese spravne reseni
        puvodniObraz.setPuzzlePossibleSolution(originalPuzzle);
        puvodniObraz.calculateFitness();

        System.out.println("Fitness spravne slozeneho obrazu je: "+puvodniObraz.getFitness());
        Config.spravnaFitness = puvodniObraz.getFitness();
        //Config.puvodniObraz = puvodniObraz;
        System.out.println();

        startovniCas = System.currentTimeMillis();

        //vytvoreni prvni generace zamichanim puvodniho obrazu
        populace = (firstGeneration(originalPuzzle));

        showStatistic(populace);

        while( pickBestChromosome(populace).getFitness() > Config.spravnaFitness ){    //(cisloPopulace + 1) < Config.pocetPopulaci
            System.out.print((cisloPopulace+1)+".generace. ");
            double osudJedince = 0;
            double nejlepsiFitness = pickBestChromosome(populace).getFitness();

            //pokud skladame narocnejsi puzzle, budeme zvysovat pravdepodobnost mutace se snizujici se fitness.
            //krizeni dostalo jiz dost prostoru a je vetsi sance najit spravne reseni mutovanim
            if (Config.verzeFitness != 0){  // pokud pocitame mannhatanskou fitness, nechame pravdepodobnost konstantni
                Config.pravdepodobnostMutace = (    Config.uspesnost * 0.7 ) + 0.1;
            }

            //prochazime populaci
            for (int i=0; i < Config.velikostPopulace; i++){

                //rozhodne, zda se bude jedinec mutovat nebo krizit
                osudJedince = Math.random();
                //vytvorim novy Chromosome do ktereho zkopiruji aktualni Chromosome z populace, provedu na nem operace a pokud ho to zlepsi vymenim ho za toho v populaci
                Chromosome kandidat = new Chromosome(populace.get(i));

                if (osudJedince < Config.pravdepodobnostMutace){ //Config.pravdepodobnostMutace
                    //mutace
                    mutate(kandidat);
                    kandidat.calculateFitness();
                }
                else if (osudJedince < 0.9){
                    //krizeni
                    crossover(kandidat);
                    kandidat.calculateFitness();
                }
                else{
                    //mutace a krizeni
                    mutate(kandidat);
                    crossover(kandidat);
                    kandidat.calculateFitness();
                }

                //pokud je kandidat lepsi nez puvodni jedinec, vymeni se
                if (kandidat.getFitness() <= populace.get(i).getFitness()){
                    populace.set(i, kandidat);
                }
            }
            if (cisloPopulace % 500 == 0){
                populace.remove(nejslabsi(populace));
                populace.add(pickBestChromosome(populace));
                populace.remove(nejslabsi(populace));
                populace.add(shuffle(pickBestChromosome(populace)));
            }

            showStatistic(populace);
            cisloPopulace++;
        }
        //Vypsani doby behu programu
        long konecnyCas = System.currentTimeMillis();
        long dobaBehuProgramu = (konecnyCas- startovniCas);
        System.out.println("Doba behu programu: "+ dobaBehuProgramu+" milisekund.");

        //vykresleni nalezeneho nejlepsiho reseni
        ResultPicture.drawAll(pickBestChromosome(populace).getPuzzlePossibleSolution());
        System.out.println();
        Config.verzeFitness = 0;
        Chromosome qwer = new Chromosome(pickBestChromosome(populace));
        qwer.calculateFitness();
        System.out.println("Manhattanska vzdalenost nejlepsiho jedince: "+qwer.getFitness()); //vypsani fitness nejlepsiho pomoci manhattanovskych vzdalenosti
    }
else if (Config.typEvoluce == 3){
        Chromosome puvodniObraz = new Chromosome();
        ArrayList<Chromosome> populace;
        int cisloPopulace = 0;

        //nastaveni nulteho jedince, ktery nese spravne reseni
        puvodniObraz.setPuzzlePossibleSolution(originalPuzzle);
        puvodniObraz.calculateFitness();

        System.out.println("Fitness spravne slozeneho obrazu je: "+puvodniObraz.getFitness());
        Config.spravnaFitness = puvodniObraz.getFitness();
        //Config.puvodniObraz = puvodniObraz;
        System.out.println();

        startovniCas = System.currentTimeMillis();

        //vytvoreni prvni generace zamichanim puvodniho obrazu
        populace = (firstGeneration(originalPuzzle));

        showStatistic(populace);

        while( pickBestChromosome(populace).getFitness() > Config.spravnaFitness ){    //(cisloPopulace + 1) < Config.pocetPopulaci
            System.out.print((cisloPopulace+1)+".generace. ");

            //pripravime novou populaci
            ArrayList<Chromosome> novaPopulace = new ArrayList(populace);

            //vybereme nastaveny pocet elitnich jedincu
            ArrayList<Chromosome> elitniJedinci = new ArrayList(populace);  //zkopirovani stare populace

            Collections.sort(elitniJedinci, new Comparator<Chromosome>() {  //serazeni od nejlepsich
            @Override public int compare(Chromosome p1, Chromosome p2) {
                return (int) (p1.getFitness() - p2.getFitness());
            }});

            //zkopirovani elit na zacatek nove populace
            for (int i=0; i < Config.pocetElit; i++){
                novaPopulace.set(i, elitniJedinci.get(i));
            }

            //naplneni zbytku nove populace
            for (int i=(Config.pocetElit - 1); i < Config.velikostPopulace; i++){
                //vytvorim novy Chromosome do ktereho zkopiruji vybrany Chromosome z populace
                Chromosome kandidat = new Chromosome(rankRulette(5, populace));

                //rozhodne, zda se bude jedinec krizit
                if(Math.random() < Config.pravdepodobnostKrizeni){
                    crossover(kandidat);
                    kandidat.calculateFitness();
                }

                //rozhodne, zda se bude jedinec mutovat
                if(Math.random() < Config.pravdepodobnostMutace){
                    mutate(kandidat);
                    kandidat.calculateFitness();
                }

                novaPopulace.set(i, kandidat);

                //zkopirovani novych jedincu do stale populace
                Collections.copy(populace, novaPopulace);
            }
            showStatistic(populace);
            cisloPopulace++;
        }
        //Vypsani doby behu programu
        long konecnyCas = System.currentTimeMillis();
        long dobaBehuProgramu = (konecnyCas- startovniCas);
        System.out.println("Doba behu programu: "+ dobaBehuProgramu+" milisekund.");

        //vykresleni nalezeneho nejlepsiho reseni
        ResultPicture.drawAll(pickBestChromosome(populace).getPuzzlePossibleSolution());
        System.out.println();
        Config.verzeFitness = 0;
        Chromosome qwer = new Chromosome(pickBestChromosome(populace));
        qwer.calculateFitness();
        System.out.println("Manhattanska vzdalenost nejlepsiho jedince: "+qwer.getFitness()); //vypsani fitness nejlepsiho pomoci manhattanovskych vzdalenosti
    }
}
}
